This invention relates to systems and methods for processing digital images. More specifically it relates to a method of image segmentation based on graph cuts that is useful for separating an object of interest in an image from the background of that object in the image. Object segmentation by finding their precise boundaries in images is well known. Different segmentation methods, including graph cuts, are well known. The graph cuts segmentation method has proven to be highly accurate in object segmentation. Applications that can strongly benefit from methods that can reliably segment out objects in images by finding their precise boundaries are in the field of medical imaging and medical diagnosis. Unsegmented images may present the viewer with overwhelming quantities of information that would make it difficult to focus on relevant parts of these images. Precise segmentation of images of organs from their background will make a potential diagnosis more reliable and easier to achieve and allows for precise volume measurements of objects such as tumors.
Graph cuts is an effective method of image segmentation that is described publicly in Y. Boykov and M.-P. Jolly, “Interactive organ segmentation using graph cuts:” in Medical Image Computing and Computer-Assisted Intervention, Pittsburgh, Pa., October 2000, pp. 276-286. Another description can be found in Y. Boykov and M.-P. Jolly “Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images,” in International Conference on Computer Vision, vol. 1, July 2001, pp. 105-112. The method of GRAPH CUT segmentation inputs two groups of “seeds” which are obtained either interactively or automatically into a multi-dimensional (2D or higher) image comprised of pixels or voxels, indicating that some voxels are “object” and others are “background”. The algorithm then proceeds to label the remaining (i.e., unlabeled) voxels as either object or background. This output is obtained by treating the volume as a graph where each voxel in a volume is associated with a node and a lattice-based neighborhood structure is imposed. By weighting the edges in the graph in accordance with intensity differences (or a model of the object boundary), the smallest cut is found between the known object/background seeds using the max-flow/min-cut algorithm developed in Y. Boykov and V. Kolmogorov, “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, September 2004.
Although the algorithm has proven effective at volume segmentation, and has continued to find application in recent work such as U.S. patent application Ser. No. 11/313,102, filed Dec. 20, 2005, which is hereby incorporated by reference, the speed and memory consumption required for evaluating large volumes continues to be problematic. One approach for overcoming this problem is to diminish the demand for computing resources in determining the graph cuts by down-sampling the to be segmented volume. This may include a method to produce coarse-level volumes that the graph cuts segmentation algorithm could be applied to. Although such an approach overcomes the speed/memory consumption problem by operating on effectively a smaller volume, it was up till the present invention unclear how to translate the coarsened solution to the original resolution volume such that the solution so obtained has a comparable quality as if the graph cuts algorithm were applied directly to full-resolution volume.
Accordingly, new and improved methods and systems are required that will create more rapid graph cuts on coarsened and thus smaller volumes with the same quality as a full-resolution volume graph cuts of an image.